import numpy as np  # 导入NumPy库，用于科学计算和数组操作
import matplotlib.pyplot as plt  # 导入Matplotlib的pyplot模块，用于数据可视化
import random  # 导入random模块，用于生成随机数
from math import sqrt  # 从math模块导入sqrt函数，用于计算平方根
import time  # 导入time模块，用于计算程序运行时间

# 生成城市坐标的函数
def generate_cities(num_cities, seed=None):
    """
    生成指定数量的随机城市坐标
    参数:
        num_cities: 城市数量
        seed: 随机种子(确保结果可复现)
    返回:
        包含城市坐标的numpy数组
    """
    if seed is not None:  # 如果提供了随机种子
        random.seed(seed)  # 设置Python内置random模块的种子
        np.random.seed(seed)  # 设置NumPy随机数生成器的种子
    
    cities = []  # 初始化空列表存储城市坐标
    for _ in range(num_cities):  # 循环生成指定数量的城市
        # 在0-100范围内随机生成x和y坐标
        x = random.uniform(0, 100)  # 生成0到100之间的随机浮点数作为x坐标
        y = random.uniform(0, 100)  # 生成0到100之间的随机浮点数作为y坐标
        cities.append((x, y))  # 将坐标作为元组添加到列表中
    
    return np.array(cities)  # 将列表转换为NumPy数组并返回

# 计算两个城市间距离的函数
def distance(city1, city2):
    """
    计算两个城市之间的欧几里得距离
    参数:
        city1, city2: 包含(x,y)坐标的元组
    返回:
        两点之间的直线距离
    """
    x1, y1 = city1  # 解包第一个城市的x和y坐标
    x2, y2 = city2  # 解包第二个城市的x和y坐标
    return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)  # 使用欧几里得距离公式计算距离

# 计算路径总长度的函数
def total_distance(path, cities):
    """
    计算给定路径的总长度
    参数:
        path: 城市访问顺序的列表
        cities: 所有城市坐标的数组
    返回:
        路径的总长度(包括返回起点)
    """
    total = 0.0  # 初始化总距离为0
    num_cities = len(path)  # 获取路径中的城市数量
    
    for i in range(num_cities):  # 遍历路径中的每个城市
        from_city = cities[path[i]]  # 获取当前城市的坐标
        to_city = cities[path[(i + 1) % num_cities]]  # 获取下一个城市的坐标(使用模运算处理最后一个城市返回起点的情况)
        total += distance(from_city, to_city)  # 累加两城市间距离
    
    return total  # 返回总距离

# 初始化种群的函数
def initialize_population(pop_size, num_cities):
    """
    生成初始种群
    参数:
        pop_size: 种群大小
        num_cities: 城市数量
    返回:
        包含随机路径的种群列表
    """
    population = []  # 初始化空列表存储种群
    base = list(range(num_cities))  # 创建基础路径[0,1,2,...,num_cities-1]
    
    for _ in range(pop_size):  # 生成指定大小的种群
        individual = base.copy()  # 复制基础路径
        random.shuffle(individual)  # 随机打乱路径顺序
        population.append(individual)  # 将个体添加到种群
    
    return population  # 返回种群

# 计算适应度的函数
def calculate_fitness(population, cities):
    """
    计算种群中每个个体的适应度
    参数:
        population: 种群列表
        cities: 城市坐标数组
    返回:
        适应度值的NumPy数组
    """
    fitness_values = []  # 初始化空列表存储适应度值
    
    for individual in population:  # 遍历种群中的每个个体
        dist = total_distance(individual, cities)  # 计算该个体的路径长度
        # 适应度取路径长度的倒数(避免除零错误)
        fitness_values.append(1 / (dist + 1e-10))  # 1e-10是极小值，防止距离为0时出现除零错误
    
    return np.array(fitness_values)  # 将适应度列表转换为NumPy数组并返回

# 轮盘赌选择函数
def roulette_wheel_selection(population, fitness_values):
    """
    使用轮盘赌选择方法选择个体
    参数:
        population: 当前种群
        fitness_values: 适应度值数组
    返回:
        被选中的个体组成的新种群
    """
    total_fitness = fitness_values.sum()  # 计算总适应度
    probabilities = fitness_values / total_fitness  # 计算每个个体被选中的概率
    
    # 根据概率选择个体(可能重复选择)
    selected_indices = np.random.choice(len(population), size=len(population), p=probabilities)
    selected_population = [population[i] for i in selected_indices]  # 根据索引获取选中的个体
    
    return selected_population  # 返回选中的种群

# 顺序交叉(OX)函数
def order_crossover(parent1, parent2):
    """
    顺序交叉(OX)操作
    参数:
        parent1, parent2: 两个父代个体
    返回:
        一个新的子代个体
    """
    size = len(parent1)  # 获取个体长度(城市数量)
    start, end = sorted(random.sample(range(size), 2))  # 随机选择两个不同的位置并排序
    
    child = [-1] * size  # 初始化子代个体(-1表示未填充位置)
    
    # 从父代1复制子序列到子代
    child[start:end+1] = parent1[start:end+1]
    
    # 用父代2中未使用的城市填充剩余位置
    pointer = 0  # 父代2的指针
    for i in range(size):  # 遍历所有位置
        if child[i] == -1:  # 如果该位置需要填充
            # 找到父代2中尚未在子代中出现的城市
            while parent2[pointer] in child:
                pointer = (pointer + 1) % size
            child[i] = parent2[pointer]  # 将该城市添加到子代
            pointer = (pointer + 1) % size  # 移动指针
    
    return child  # 返回子代个体

# 交换变异函数
def swap_mutation(individual, mutation_rate):
    """
    执行交换变异操作
    参数:
        individual: 个体路径
        mutation_rate: 变异概率
    返回:
        可能变异后的个体
    """
    if random.random() < mutation_rate:  # 以mutation_rate的概率执行变异
        # 随机选择两个不同的位置
        idx1, idx2 = random.sample(range(len(individual)), 2)
        # 交换这两个位置的城市
        individual[idx1], individual[idx2] = individual[idx2], individual[idx1]
    
    return individual  # 返回(可能变异后的)个体

# 精英保留策略函数
def elitism(population, fitness_values, new_population, elite_size=1):
    """
    精英保留策略，将最优个体保留到下一代
    参数:
        population: 当前种群
        fitness_values: 当前种群的适应度值
        new_population: 新生成的种群
        elite_size: 保留的精英个体数量
    返回:
        包含精英个体的新种群
    """
    # 获取适应度最高的精英个体索引
    best_indices = np.argsort(fitness_values)[-elite_size:]
    
    # 用精英个体替换新种群中的较差个体
    for i, idx in enumerate(best_indices):
        new_population[i] = population[idx].copy()  # 复制精英个体到新种群
    
    return new_population  # 返回更新后的新种群

# 绘制路径图的函数
def plot_path(cities, path, title="TSP Path"):
    """
    可视化展示TSP路径
    参数:
        cities: 城市坐标数组
        path: 城市访问顺序
        title: 图表标题
    """
    x = [city[0] for city in cities]  # 提取所有x坐标
    y = [city[1] for city in cities]  # 提取所有y坐标
    
    plt.figure(figsize=(10, 6))  # 创建新图形，设置大小
    
    # 绘制城市点
    plt.scatter(x, y, c='red', s=100)  # 红色点，大小100
    
    # 绘制路径线
    path_x = [x[i] for i in path] + [x[path[0]]]  # 路径的x坐标(包含返回起点)
    path_y = [y[i] for i in path] + [y[path[0]]]  # 路径的y坐标(包含返回起点)
    plt.plot(path_x, path_y, 'b-')  # 蓝色实线
    
    # 标记起点(绿色星号)
    plt.scatter(x[path[0]], y[path[0]], c='green', s=150, marker='*', label='Start')
    
    # 为每个城市添加标签
    for i, (xi, yi) in enumerate(zip(x, y)):
        plt.annotate(f"{i}", (xi, yi), fontsize=12)  # 在城市旁标注索引
    
    plt.title(title)  # 设置标题
    plt.xlabel("X Coordinate")  # x轴标签
    plt.ylabel("Y Coordinate")  # y轴标签
    plt.legend()  # 显示图例
    plt.grid(True)  # 显示网格
    plt.show()  # 显示图形

# 遗传算法主函数
def genetic_algorithm_tsp(cities, pop_size=100, elite_size=5, mutation_rate=0.01, generations=500):
    """
    使用遗传算法求解TSP问题
    参数:
        cities: 城市坐标数组
        pop_size: 种群大小
        elite_size: 精英保留数量
        mutation_rate: 变异率
        generations: 迭代代数
    返回:
        最优路径和最优路径长度
    """
    num_cities = len(cities)  # 获取城市数量
    
    # 1. 初始化种群
    population = initialize_population(pop_size, num_cities)
    
    # 记录最佳解和进化历史
    best_individual = None  # 存储最佳个体
    best_fitness = -np.inf  # 最佳适应度(初始为负无穷)
    history = []  # 存储每代最佳路径长度的历史记录
    
    # 迭代进化过程
    for gen in range(generations):  # 遍历每一代
        # 2. 计算适应度
        fitness_values = calculate_fitness(population, cities)
        
        # 3. 记录当前最佳解
        current_best_idx = np.argmax(fitness_values)  # 当前最佳个体的索引
        current_best_fitness = fitness_values[current_best_idx]  # 当前最佳适应度
        current_best_individual = population[current_best_idx]  # 当前最佳个体
        
        # 更新全局最佳解
        if current_best_fitness > best_fitness:
            best_fitness = current_best_fitness
            best_individual = current_best_individual.copy()  # 深拷贝最佳个体
        
        # 记录历史数据(最佳路径长度)
        history.append(1 / best_fitness)
        
        # 4. 选择操作
        selected_population = roulette_wheel_selection(population, fitness_values)
        
        # 5. 交叉操作(生成新种群)
        new_population = []
        # 每次处理两个父代，生成两个子代
        for i in range(0, pop_size, 2):
            parent1 = selected_population[i]
            parent2 = selected_population[i+1]
            
            # 交叉产生两个后代
            child1 = order_crossover(parent1, parent2)
            child2 = order_crossover(parent2, parent1)
            
            new_population.extend([child1, child2])
        
        # 6. 变异操作
        for i in range(len(new_population)):
            new_population[i] = swap_mutation(new_population[i], mutation_rate)
        
        # 7. 精英保留策略
        new_population = elitism(population, fitness_values, new_population, elite_size)
        
        # 更新种群
        population = new_population
        
        # 每50代打印进度
        if gen % 50 == 0:
            print(f"Generation {gen}: Best Distance = {1/best_fitness:.2f}")
    
    # 最终结果输出
    best_distance = 1 / best_fitness  # 计算最佳路径长度
    print("\nGenetic Algorithm Completed!")
    print(f"Best Distance: {best_distance:.2f}")
    print(f"Best Path: {best_individual}")
    
    # 绘制进化过程
    plt.figure(figsize=(10, 6))
    plt.plot(history)
    plt.title("Evolution of Best Distance")
    plt.xlabel("Generation")
    plt.ylabel("Distance")
    plt.grid(True)
    plt.show()
    
    # 绘制最佳路径
    plot_path(cities, best_individual, f"Best TSP Path (Distance: {best_distance:.2f})")
    
    return best_individual, best_distance  # 返回最优路径和长度

# 主程序入口
if __name__ == "__main__":
    # 设置随机种子确保结果可复现
    random_seed = 42
    
    # 算法参数配置
    num_cities = 20        # 城市数量
    population_size = 200   # 种群大小
    elite_size = 10         # 精英保留数量
    mutation_rate = 0.02    # 变异率
    generations = 1000      # 迭代次数
    
    # 生成城市坐标
    cities = generate_cities(num_cities, seed=random_seed)
    
    print(f"Solving TSP with {num_cities} cities using Genetic Algorithm...")
    start_time = time.time()  # 记录开始时间
    
    # 运行遗传算法求解TSP
    best_path, best_distance = genetic_algorithm_tsp(
        cities,
        pop_size=population_size,
        elite_size=elite_size,
        mutation_rate=mutation_rate,
        generations=generations
    )
    
    # 计算并打印运行时间
    end_time = time.time()
    print(f"\nExecution Time: {end_time - start_time:.2f} seconds")